/*
 * @lc app=leetcode.cn id=2121 lang=typescript
 *
 * [2121] 相同元素的间隔之和
 */

// @lc code=start
function getDistances(arr: number[]): number[] {
  const n = arr.length;
  // 下标排序
  const idxs = new Array(n).fill(0).map((_, i) => i);
  // 对数组按照数字升序排序，如果数字相同，按照下标升序
  idxs.sort((a, b) => {
    if (arr[a] !== arr[b]) {
      return arr[a] - arr[b];
    }
    return a - b;
  });

  const ans = new Array(n).fill(0);
  for (let i = 0, j = 0; i < n; i = j + 1) {
    j = i;
    // 找到相同数字的区间
    while (j + 1 < n && arr[idxs[j + 1]] === arr[idxs[i]]) j++;
    let sum_pre = 0;
    let sum_next = 0;
    for (let k = i; k <= j; k++) sum_next += idxs[k];
    for (let k = i; k <= j; k++) {
      sum_next -= idxs[k];
      ans[idxs[k]] = (k - i) * idxs[k] - sum_pre + (sum_next - (j - k) * idxs[k]);
      sum_pre += idxs[k];
    }
  }

  return ans;
}
// @lc code=end
